package offer_test_40;

import java.util.Arrays;

//：输入n个整数，找出其中最小的k个数。例如输入4,5,1，6,2,7,3,8这8个数字，则最少的4个数字是1,2,3,4.
public class ten_KLeastNum {
	public static void main(String[] args) throws Exception {
		int[] array = { 4, 5, 1, 6, 2, 7, 3, 8 };
		int k = 9;
		methodone(array,  k);
	}

	public static void methodone(int[] array,int k) throws Exception {
//		int mid = array[array.length / 2 - 1];
		int head = 0;
		int tail = array.length - 1;
		if (array.length <k) {
			throw new Exception("参数错误");
		}
		array=methodeone_getNum(array, head, tail, k);
		for(int i=0;i<k;i++){
			System.out.print(array[i]+" ");
		}
	}

	public static int[] methodeone_getNum(int[] array, int head, int tail,int k)
			throws Exception {
		if (array.length == 0 || head < 0 || tail > array.length - 1) {
			throw new Exception("参数错误");
		}
		int mid = array[head];
		while (head < tail) {
			while (head < tail && mid < array[tail]) {
				tail--;
			}
			array[head] = array[tail];
			while (head < tail && mid > array[head]) {
				head++;
			}
			array[tail] = array[head];
		}
		array[head] = mid;
		if(head==k-1){
			return array;
		}else if(head>k-1){
			return methodeone_getNum(array, 0, head-1, k);
		}else{
			return methodeone_getNum(array, head+1, array.length-1, k);
		}
	}
}
